A digital signature scheme, which is a kind of public key cryptosystem, is provided as a technology for preventing a sender from being identified and data from being tempered during the transmission of the data from a receiving apparatus to a transmitting apparatus.
In the digital signature scheme, the transmitting apparatus generates signature data for the data to be transmitted, using a private key of the transmitting apparatus, and transmits the data and the signature data to the receiving apparatus. The receiving apparatus verifies the signature data using a public key of the transmitting apparatus, and judges whether or not the data has been tampered (e.g. see Non-Patent Reference 1). Note that it is difficult to calculate a value of the private key using the public key.
An NTRU (a trademark of NTRU cryptosystems, Inc.) cryptosystem was proposed as a public key cryptosystem capable of high-speed processing (e.g. see Non-Patent Reference 2). In the NTRU cryptosystem, encryption and decryption are performed using polynomial operations which enable computation at a speed higher than the speed achieved in RSA (Rivest Shamir Adleman) cryptosystem, in which modulo exponentiation is performed under certain modulo, and also higher than the speed achieved in an elliptic-curve cryptosystem in which scalar multiplications are performed on points on an elliptic curve. It is therefore possible to perform processing of a higher speed than the existing public key cryptosystems, and software processing can be carried out within a practical period of time.
Thus, encrypted communication systems using the NTRU cryptosystem for a public key cryptosystem have an advantage in that processing between a transmitting apparatus and a receiving apparatus can be performed at a speed higher than those achieved in the encrypted communication systems using the existing public key cryptosystem.
The method suggested in the Non-Patent Reference 2 is a confidentiality cryptosystem for encrypting data; however, later on, a digital signature scheme based on the NTRU cryptosystem is proposed (e.g. see Non-Patent Reference 3). This digital signature scheme has been modified several times due to the arrival of decryption methods.
The following briefly describes a digital signature scheme called NTRUSign (hereinafter referred to as “NTRUSign signature scheme”) (e.g. see Patent Reference 1 and Non-Patent Reference 4).
<NTRUSign Signature Scheme>
(1) Parameters in NTRUSign Signature Scheme
In the NTRUSign signature scheme, non-negative integer parameters such as N, q, df, dg and Normbound are used. The following explains the meanings of these parameters.
(i) Parameter N
The NTRUSign signature scheme is a digital signature scheme which performs signature generation and signature verification using polynomial operations. The degree of polynomials used in the NTRUSign signature scheme is determined by the parameter N mentioned above.
The polynomials used in the NTRUSign signature scheme are integer coefficient polynomials of degree (N−1) or lower with respect to the parameter N, e.g. X^4+X^3+1 when N=5. Here, “X^a” shall denote the a th power of X. Also, a public key h and a signature s are both expressed as polynomials of degree (N−1) or lower. A private key is a set of four pair polynomials (f, g, F, G) of degree (N−1) or lower. That is to say, f, g, F and G are all polynomials of degree (N−1) or lower. Note that, hereinafter, a set of (f, g, F, G) made up of four polynomials may be represented as {(f, g), (F, G)}, in some cases, regarding the set to be made up of two pairs of (f, g) and (F, G).
A polynomial operation is computed so that the computation always results in a polynomial of degree (N−1) or lower, using the relational expression X^N=1 with respect to the parameter N. For example, assuming that × presents a product of a polynomial and a polynomial, and “·” presents a product of an integer and a polynomial (or a product of an integer and an integer), when N=5, a product of the polynomial X^4+X^2+1 and the polynomial X^3+X is computed as indicated below, using the relational expression X^5=1, so that the computation always results in a polynomial of degree N−1 or lower.
            (                        X          ^          4                +                  X          ^          2                +        1            )        ×          (                        X          ^          3                +        X            )        =                    X        ^        7            +              2        ·                  X          ^          5                    +              2        ·                  X          ^          3                    +      X        ⁢                  ⁢                  =                                        X            ^            2                    ·          1                +                  2          ·          1                +                  2          ·                      X            ^            3                          +        X            ⁢                          ⁢                          =                        2          ·                      X            ^            3                          +                  X          ^          2                +        X        +        2            
Note that, in the NTRUSign signature scheme, a polynomial a of degree (N−1) expressed as a=a—0+a—1·X+a—2·X^2+ . . . +a_(N−1)·X^(N−1) is identified as a vector (a—0, a—1, a—2, . . . , a_(N−1)). Here, a—0, a—1, a—2, . . . , a_(N−1) are coefficients of the polynomial a, and are integer numbers.
(ii) Parameter q
In the NTRUSign signature scheme, a parameter q, which is an integer number of 2 or greater, is used. The coefficients in a polynomial that appears in the NTRUSign signature scheme obtain remainder modulo q.
(iii) Parameters df and dg
The method for selecting a polynomial f which is a part of the private keys used in the NTRUSign signature scheme and a polynomial g to be used together with the polynomial f for generating a public key polynomial h is determined based on the parameters df and dg.
First, the polynomial f is selected so that df coefficients indicate “1”, and other coefficients indicate “0”. In other words, the polynomial f is a polynomial of degree (N−1) or lower, having N coefficients that range from coefficients of degree 0 (constant term) to degree (N−1), and the polynomial f is selected so that df coefficients indicate “1”, and (N−df) coefficients indicate “0” out of such N coefficients. The polynomial g is then selected so that dg coefficients indicate “1”, and other coefficients indicate “0”.
(iv) Parameter Normbound
In the NTRUSign signature scheme, a distance between a 2·N-degree vector created from the signature s, and a 2·N-degree vector which is a hash value of message data (hereinafter simply referred to as “message”) is calculated, and whether or not the signature s is an authorized signature is judged based on the distance. Normbound is a threshold value to be used for the judgment. That is to say, in the case where the distance is smaller than Normbound, the signature s is accepted as an authorized signature, while in the case where the distance equals to or greater than Normbound, the signature s is denied as an unauthorized signature. Note that the Non-Patent Reference 4 introduces an example of (N, q, df, dg, Normbound)=(251, 128, 73, 71, 310) as an example of the parameters in the NTRUSign signature scheme.
(2) Hash Value of Message and Distance Between Norm and Vector
In the NTRUSign signature scheme, a signature is created for a hash value of a message. The hash value of the message is a pair of polynomials of degree N, and is identified as a 2·N-degree vector. Note that the Non-Patent Reference 1 describes in detail hash function for deriving a hash value based on a message.
In the NTRUSign signature scheme, a distance between vectors is used in signature verification, and a norm (Centered norm) is used for the calculation of such a distance. The following defines a distance between a norm and a vector.
A norm ∥a∥ of the polynomial a=a—0+a—1·X+a—2·X^2+ . . . +a_(N−1)·X^(N−1) is defined as below.∥a∥=sqrt((a—0−μ)^2+(a—1−μ)^2+ . . . +(a_(N−1)−μ)^2)μ=(1/N)·(a—0+a—1+a—2+ . . . +a_(N−1))
Here, sqrt(x) shows a square root of x.
A norm ∥(a,b)∥ of the pair (a,b) for the polynomials a and b is defined as indicated below.∥(a,b)∥=sqrt(∥a∥^2+∥b∥^2)
A distance (inter-vector distance) between the pair (a,b) of the polynomials a and b and the pair (c,d) of the polynomials c and d is defined as ∥(c−a, d−b)∥.
(3) Key Generation in the NTRUSign Signature Scheme
As described above, in the NTRUSign signature scheme, the polynomials f and g are generated at random using the parameters df and dg. As is described in the Non-Patent Reference 4, the polynomial h is generated using the polynomial Fq which satisfies Fq×f=1(mod q) by the expression h=Fq×g(mod q). Moreover, the polynomials F and G with small norms are derived so as to satisfy the following expression.f×G−g×F=q 
Here, it is assumed that {(f,g), (F,G)} denotes a private key and h denotes a public key. The private key is a key for generating a signature and is also called a signature generation key. The public key is a key for verifying the signature and is also called a signature verification key.
Here, x=y(mod q) is an operation which obtains, as the coefficient of i th degree in the polynomial x, a remainder obtained when the coefficient of i th degree in the polynomial y is divided by q so that the remainder indicates a value ranging from 0 to (q−1) (0≦i≦N−1). That is to say that it is an operation which obtains, as the polynomial x, a polynomial to which the (mod q) operation is performed so that each of the coefficients in the polynomial y indicates a value ranging from “0” to “(q−1)”.
(4) Signature Generation in the NTRUSign Signature Scheme
In the signature generation according to the NTRUSign signature scheme, a signature s of a message m for which a signature should be generated is calculated. First, a 2·N-degree vector (m1, m2) (m1 and m2 are polynomials of degree N), which is a hash value for the message m, is calculated.
The polynomials a, b, A and B are calculated so as to satisfy the expression below using the 2·N-degree vector (m1, m2) and the private key {(f,g), (F, G)}.G×m1−F×m2=A+q×B −g×m1+f×m2=a+q×b 
Here, it is presumed that each of the coefficients in the polynomials A and a is remainder obtained when divided by q so that the remainder indicates a value ranging from “<−q/2>+1” to “<q/2>”. In other words, in the case where the remainder obtained when divided by q indicates a value ranged from “<q/2>” to “q−1”, the remainder is adjusted through the subtraction of q so as to fall within the above-mentioned range. Here, <x> indicates the largest value within the values indicating x or smaller. For example, <−½>=−1.
Next, polynomials s and t are calculated using the expressions below, and the polynomial s is outputted as a signature.s=f×B+F×b(mod q)t=g×B+G×b(mod q)
FIG. 1 is a diagram for describing how to generate a signature s.
In the NTRUSign signature scheme, a nearest-neighbor lattice point P of a hash value H(m)=(m1, m2) for the message m is derived based on the above expressions s=f×B+F×b (mod q) and t=g×B+G×b (mod q), on a lattice of degree 2·N extended by a private key sequence {(f, g), (F, G)}. That is to say, a lattice point that is the nearest to (m1, m2) is found out as the nearest-neighbor lattice point P. Then, only the polynomial s of a signature vector (s, t) indicating the nearest-neighbor lattice point P is treated as a signature.
(5) Signature Verification in the NTRUSign Signature Scheme
In the signature verification according to the NTRUSign signature scheme, whether or not the signature s is an authorized signature of the message m for which the signature s has been generated is verified. First, a 2·N-degree vector (m1, m2) which is a hash value for a message m is calculated.
The polynomial t is calculated based on the following expression using the public key h.t=s×h(mod q)
A distance between the 2·N-degree vectors (s, t) and (m1, m2) is obtained, and whether or not the distance is smaller than Normbound is checked. In the case where the distance is smaller than Normbound, the signature s is judged to be authorized and then accepted. In the case where the distance equals to or greater than Normbound, the signature s is judged to be unauthorized and then denied.
FIG. 2 is a diagram for describing a method for verifying a signature s.
In the NTRUSign signature scheme, the lattice point P (s, t) in the 2·N-degree lattice extended by a public key sequence {(1, h), (0, q)} is derived based on the above-mentioned expression t=s×h (mod q) using the signature s and the public key h. Here, in such a 2·N-degree lattice, it is judged whether or not the hash value H(m)=(m1, m2) for a message m is within a hypersphere whose radius equals to Normbound with the lattice point P(s, t) in the center. In the case where the hash value is within the hypersphere, the signature s is judged to be authorized and then accepted, whereas in the case where the hash value is not within the hypersphere, the signature s is judged to be unauthorized and then denied.
Patent Reference 1: International Publication Bulletin No. 03/050998.
Non-Patent Reference 1: Tatsuaki Okamoto, and Hirosuke Yamamoto, Modern Cryptography, Sangyo Tosho, 1997.
Non-Patent Reference 2: Silverman, “NTRU: A ring based public key cryptosystem”, Lecture Notes in Computer Science, 1423, pp. 267-288, Springer-Verlag, 1998.
Non-Patent Reference 3: J. Hoffstein, J. Pipher and 3. Silverman, “NSS: An NTRU Lattice-Based Signature Scheme”, Advances in Cryptoplogy-Eurocrycpt '01, LINCS, Vol. 2045, pp. 123-137, Springer-Verlag, 2001.
Non-Patent Reference 4: J. Hoffstein, N. Graham, J. Pipher, J. Silverman and W. Whyte, “NTRUSign: Digital Signatures Using the NTRU Lattice”, CT-RSA '03, LNCS, Vol. 2612, pp. 122-140, Springer-Verlag, 2003.
Patent Reference 5: S. Min, G. Yamamoto and K. Kim, “On the security of NTRUSign signature scheme”, SCIS2004.